// 13.6 对象移动
/**
 * 新标准的一个最主要的特性是可以移动而非拷贝对象的能力。如我们在13.1.1节（第440页）中所见，很多情况下都会发生对象拷贝。
 * 在其中某些情况下，对象拷贝后就立即被销毁了。在这些情况下，移动而非拷贝对象会大幅度提升性能。
 * 使用移动而不是拷贝的另一个原因源于IO类或unique_ptr这样的类。这些类都包含不能被共享的资源（如指针或IO缓冲）。因此，这些类型的对象不能拷贝但可以移动。
 * 标准库容器、string和shared_ptr类既支持移动也支持拷贝。IO类和unique_ptr类可以移动但不能拷贝。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;

// 类vector类内存分配策略的简化实现
class StrVec
{
public:
    StrVec(): // 默认构造函数（隐式地）默认初始化alloc并（显式地）将指针初始化为nullptr，表明没有元素。
        elements(nullptr), first_free(nullptr), cap(nullptr) {}
    StrVec(const StrVec&);            // 拷贝构造函数
    StrVec& operator=(const StrVec&); // 拷贝赋值运算符
    ~StrVec();                        // 析构函数
    void push_back(const std::string&); // 拷贝元素
    size_t size() const { return first_free - elements; }
    size_t capacity() const { return cap - elements;}
    std::string *begin() const { return elements; } // begin和end成员分别返回指向首元素（即elements）和最后一个构造的元素之后位置（即first_free）的指针。
    std::string *end() const { return first_free; }
    pair<string*, string*> alloc_n_copy(const string *b, const string *e);
    StrVec(StrVec &&s) noexcept; // 移动构造函数，不同于拷贝构造函数，移动构造函数的第一个参数为右值引用
    StrVec& operator=(StrVec &&rhs) noexcept; // 移动赋值运算符
    
private:
    std::string *elements;   // 指向数组首元素的指针
    std::string *first_free; // 指向数组第一个空闲元素的指针
    std::string *cap;        // 指向数组尾后位置的指针
    void free();             // 销毁元素并释放内存
    void reallocate();       // 获得更多内存并拷贝已有元素
    static std::allocator<std::string> alloc; // 分配元素
    // 被添加元素函数所使用
    void check_n_alloc() { if(size() == capacity()) reallocate(); }
};
// 为StrVec类定义移动构造函数，实现从一个StrVec到另一个StrVec的元素移动而非拷贝：
StrVec::StrVec(StrVec &&s) noexcept // noexcept在这里代表，移动操作不应抛出任何异常
    : elements(s.elements), first_free(s.first_free), cap(s.cap)
{
    // 令s进入这样的状态————对其运行析构函数是安全的
    s.elements = s.first_free = s.cap = nullptr;
    // 与拷贝构造函数不同，移动构造函数不分配任何新内存；它接管给定的StrVec中的内存。在接管内存之后，它将给定对象中的指针都置为nullptr。
}
// 移动赋值运算符执行与析构函数和移动构造函数相同的工作。与移动构造函数一样，如果我们的移动赋值运算符不抛出任何异常，我们就应该将它标记为noexcept。
StrVec& StrVec::operator=(StrVec &&rhs) noexcept
{
    // 直接检测自赋值
    // 在此例中，我们直接检查this指针与rhs的地址是否相同。如果相同，右侧和左侧运算对象指向相同的对象，我们不需要做任何事情。
    if(this != &rhs)
    {
        free(); // 释放已有元素
        elements = rhs.elements; // 从rhs接管资源
        first_free = rhs.first_free;
        cap = rhs.cap;
        // 将rhs置于可析构状态
        rhs.elements = rhs.first_free = rhs.cap = nullptr;
    }
    return *this;
}
void StrVec::push_back(const std::string &s)
{
    check_n_alloc(); // 确保有空间容纳新元素
    // 在first_free指向的元素中构造s的副本
    alloc.construct(first_free++, s);
    // 当我们用allocator分配内存时，必须记住内存是未构造的（参见12.2.2节，第428页）。
    // 为了使用此原始内存，我们必须调用construct，在此内存中构造一个对象。传递给construct的第一个参数必须是一个指针，指向调用allocate所分配的未构造的内存空间。
    // 剩余参数确定用哪个构造函数来构造对象。在本例中，只有一个额外参数，类型为string，因此会使用string的拷贝构造函数。
    // 值得注意的是，对construct的调用也会递增first_free，表示已经构造了一个新元素。
    // 它使用前置递增（参见4.5节，第131页），因此这个调用会在first_free当前值指定的地址构造一个对象，并递增first_free指向下一个未构造的元素。

    // 前置递增运算符，首先将运算对象+1，然后将改变后的对象作为求值结果。
    // 后置递增运算符，也会将运算对象+1，但是求值结果是运算对象改变之前那个值的副本。
    // int i=0, j;
    // j = ++i;  // j=1, i=1，前置版本得到递增之后的值
    // j = i++;  // j=1, i=2，后置版本得到递增之前的值
}
// alloc_n_copy成员会分配足够的内存来保存给定范围的元素，并将这些元素拷贝到新分配的内存中。
// 此函数返回一个指针的pair（参见11.2.3节，第379页），两个指针分别指向新空间的开始位置和拷贝的尾后的位置：
pair<string*, string*> StrVec::alloc_n_copy(const string *b, const string *e)
{
    // 分配空间保存给定范围中的元素
    auto data = alloc.allocate(e - b); // end - begin
    // 初始化并返回一个pair，该pair由data和uninitialized_copy的返回值构成
    return {data, uninitialized_copy(b, e, data)};
    // 返回的pair的first成员指向分配的内存的开始位置；second成员则是uninitialized_copy（参见12.2.2节，第429页）的返回值，此值是一个指针，指向最后一个构造元素之后的位置。
}
// free成员有两个责任：首先destroy元素，然后释放StrVec自己分配的内存空间。
// for循环调用allocator的destroy成员，从构造的尾元素开始，到首元素为止，逆序销毁所有元素：
void StrVec::free()
{
    // 不能传递给deallocate一个空指针，如果elements为0，函数什么也不做
    if(elements)
    {
        // 逆序销毁旧元素
        for(auto p=first_free; p!=elements; /* 空 */)
            alloc.destroy(--p); // destroy函数会运行string的析构函数。string的析构函数会释放string自己分配的内存空间。
        alloc.deallocate(elements, cap-elements);
        // 一旦元素被销毁，我们就调用deallocate来释放本StrVec对象分配的内存空间。
        // 我们传递给deallocate的指针必须是之前某次allocate调用所返回的指针。因此，在调用deallocate之前我们首先检查elements是否为空。
    }
}
// 拷贝控制成员
StrVec::StrVec(const StrVec &s)
{
    // 调用alloc_n_copy分配空间以容纳与s中一样多的元素
    auto newdata = alloc_n_copy(s.begin(), s.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
    // alloc_n_copy的返回值是一个指针的pair。其first成员指向第一个构造的元素，second成员指向最后一个构造的元素之后的位置。
    // 由于alloc_n_copy分配的空间恰好容纳给定的元素，cap也指向最后一个构造的元素之后的位置。
}
// 析构函数调用free
StrVec::~StrVec() { free(); }
// 拷贝赋值运算符在释放已有元素之前调用alloc_n_copy，这样就可以正确处理自赋值了：
StrVec& StrVec::operator=(const StrVec &rhs)
{
    // 调用alloc_n_copy分配内存，大小与rhs中元素占用空间一样多
    auto data = alloc_n_copy(rhs.begin(), rhs.end());
    free();
    elements = data.first;
    first_free = cap = data.second;
    return *this;
}
// reallocate成员
void StrVec::reallocate()
{
    // 我们将分配当前大小两倍的内存空间，如果StrVec为空，我们将分配容纳一个元素的空间：
    auto newcapacity = size() ? 2*size() : 1;
    // 分配新内存
    auto newdata = alloc.allocate(newcapacity);
    // 将数据从旧内存移动到新内存
    auto dest = newdata;  // 指向新数据中下一个空闲位置？
    auto elem = elements; // 指向旧数组中下一个元素？这不是旧数组中第一个元素吗？
    for(size_t i =0; i!=size(); ++i)
        alloc.construct(dest++, std::move(*elem++));
    free(); // 一旦我们移动完元素就释放旧内存空间
    // 更新我们的数据结构，执行新元素
    elements = newdata;
    first_free = dest;
    cap = elements + newcapacity;

    // 在重新分配内存的过程中移动而不是拷贝元素在编写reallocate成员函数之前，我们稍微思考一下此函数应该做什么。
    // 它应该:1.为一个新的、更大的string数组分配内存 2.在内存空间的前一部分构造对象，保存现有元素 3.销毁原内存空间中的元素，并释放这块内存
    // 由于string的行为类似值，我们可以得出结论，每个string对构成它的所有字符都会保存自己的一份副本。拷贝一个string必须为这些字符分配内存空间，而销毁一个string必须释放所占用的内存。
    // 因此，拷贝这些string中的数据是多余的。在重新分配内存空间时，如果我们能避免分配和释放string的额外开销，StrVec的性能会好得多。

    // 通过使用新标准库引入的两种机制，我们就可以避免string的拷贝。首先，有一些标准库类，包括string，都定义了所谓的“移动构造函数”。
    // 关于string的移动构造函数如何工作的细节，以及有关实现的任何其他细节，目前都尚未公开。但是，我们知道，移动构造函数通常是将资源从给定对象“移动”而不是拷贝到正在创建的对象。
    // 我们使用的第二个机制是一个名为move的标准库函数，它定义在utility头文件中。目前，关于move我们需要了解两个关键点。
    // 首先，当reallocate在新内存中构造string时，它必须调用move来表示希望使用string的移动构造函数，原因我们将在13.6.1节（第470页）中解释。
    // 如果它漏掉了move调用，将会使用string的拷贝构造函数。
    // 其次，我们通常不为move提供一个using声明（参见3.1节，第74页），原因将在18.2.3节（第706页）中解释。当我们使用move时，直接调用std：：move而不是move。

    // 移动元素
    auto first = alloc.allocate(newcapacity);
    auto last = uninitialized_copy(make_move_iterator(begin()),make_move_iterator(end()),first);
    free(); // 释放旧空间
    elements = first;
    first_free = last;
    cap = elements + newcapacity;


}

// 编译器会为X和hasX合成移动操作
struct X 
{
    int i;         // 内置类型可以移动
    std::string s; // string定义了自己的移动操作
};
struct hasX
{
    X mem;         // X有合成的移动操作
};


class Foo
{
public:
    Foo() = default;
    Foo(const Foo&); // 拷贝构造函数
    // 其他成员定义，但Foo未定义移动构造函数
};

// 类值版本的HasPtr
class HasPtr
{
    friend void swap(HasPtr&, HasPtr&);
public:
    // 添加的移动构造函数
    HasPtr(HasPtr &&p) noexcept : ps(p.ps), i(p.i) { p.ps = 0 ;}
    // 赋值运算符既是移动赋值运算符，也是拷贝赋值运算符

    HasPtr(const string &s = string()) : ps(new string(s)), i(0) {}
    HasPtr(const HasPtr &p) : ps(new string(*p.ps)), i(p.i) {} // 对ps指向的string，每个HasPtr对象都有自己的拷贝
    // HasPtr &operator=(const HasPtr &);                         // 声明赋值运算符，但还未定义
    ~HasPtr() { delete ps; }
    HasPtr &operator=(HasPtr); // 赋值运算符既是移动赋值运算符，也是拷贝赋值运算符

private:
    string *ps;
    int i;
};
// // 定义赋值运算符
// HasPtr &HasPtr::operator=(const HasPtr &rhs)
// {
//     auto newp = new string(*rhs.ps); // 拷贝底层string
//     delete ps;                       // 释放旧内存
//     ps = newp;                       // 从右侧运算对象拷贝数据到本对象
//     i = rhs.i;
//     return *this;
// }
inline // 由于swap的存在就是为了优化代码，我们将其声明为inline函数（参见6.5.2节，第213页）。
void swap(HasPtr &lhs, HasPtr &rhs)
{
    using std::swap;
    swap(lhs.ps, rhs.ps); // 交换指针，而不是交换string数据
    swap(lhs.i, rhs.i);   // 交换int成员
}
// 在这个版本的赋值运算符中，参数并不是一个引用，我们将右侧运算对象以传值方式传递给了赋值运算符。因此，rhs是右侧运算对象的一个副本。
// 注意rhs是按值传递的，意味着HasPtr的拷贝构造函数将右侧运算对象中的string拷贝到rhs
HasPtr& HasPtr::operator=(HasPtr rhs)
{
    swap(*this,rhs); // rhs现在指向本对象曾经使用的内存
    return *this;    // rhs被销毁，从而delete了rhs中的指针
}

int main()
{
    // 13.6.2 移动构造函数和移动赋值运算符
    // 为了让我们自己的类型支持移动操作，需要为其定义移动构造函数和移动赋值运算符。这两个成员类似对应的拷贝操作，但它们从给定对象“窃取”资源而不是拷贝资源。
    // 类似拷贝构造函数，移动构造函数的第一个参数是该类类型的一个引用。不同于拷贝构造函数的是，这个引用参数在移动构造函数中是一个右值引用。与拷贝构造函数一样，任何额外的参数都必须有默认实参。
    // 除了完成资源移动，移动构造函数还必须确保移后源对象处于这样一个状态————销毁它是无害的。特别是，一旦资源完成移动，源对象必须不再指向被移动的资源——这些资源的所有权已经归属新创建的对象。

    // 移动操作、标准库容器和异常
    // 由于移动操作“窃取”资源，它通常不分配任何资源。因此，移动操作通常不会抛出任何异常。当编写一个不抛出异常的移动操作时，我们应该将此事通知标准库。
    // 一种通知标准库的方法是在我们的构造函数中指明noexcept。noexcept是新标准引入的，我们将在18.1.4节（第690页）中讨论更多细节。
    // 我们在一个函数的参数列表后指定noexcept。在一个构造函数中，noexcept出现在参数列表和初始化列表开始的冒号之间。
    // 我们必须在类头文件的声明中和定义中（如果定义在类外的话）都指定noexcept。
    // 不抛出异常的移动构造函数和移动赋值运算符必须标记为noexcept。
    // 除非vector知道元素类型的移动构造函数不会抛出异常，否则在重新分配内存的过程中，它就必须使用拷贝构造函数而不是移动构造函数。
    // 如果希望在vector重新分配内存这类情况下对我们自定义类型的对象进行移动而不是拷贝，就必须显式地告诉标准库我们的移动构造函数可以安全使用。
    // 我们通过将移动构造函数（及移动赋值运算符）标记为noexcept来做到这一点。

    // 移后源对象必须可析构
    // 从一个对象移动数据并不会销毁此对象，但有时在移动操作完成后，源对象会被销毁。因此，当我们编写一个移动操作时，必须确保移后源对象进入一个可析构的状态。
    // 我们的StrVec的移动操作满足这一要求，这是通过将移后源对象的指针成员置为nullptr来实现的。
    // 在移动操作之后，移后源对象必须保持有效的、可析构的状态，但是用户不能对其值进行任何假设。

    // 合成的移动操作
    // 与处理拷贝构造函数和拷贝赋值运算符一样，编译器也会合成移动构造函数和移动赋值运算符。
    // 与拷贝操作不同，编译器根本不会为某些类合成移动操作。
    // 特别是，如果一个类定义了自己的拷贝构造函数、拷贝赋值运算符或者析构函数，编译器就不会为它合成移动构造函数和移动赋值运算符了。因此，某些类就没有移动构造函数或移动赋值运算符。
    // 我们将在第477页所见，如果一个类没有移动操作，通过正常的函数匹配，类会使用对应的拷贝操作来代替移动操作。
    // 只有当一个类没有定义任何自己版本的拷贝控制成员，且类的每个非static数据成员都可以移动时，编译器才会为它合成移动构造函数或移动赋值运算符。
    // 编译器可以移动内置类型的成员。如果一个成员是类类型，且该类有对应的移动操作，编译器也能移动这个成员：
    X x, x2 = std::move(x);       // 使用合成的移动构造函数
    hasX hx, hx2 = std::move(hx); // 使用合成的移动构造函数
    // 只有当一个类没有定义任何自己版本的拷贝控制成员，且它的所有数据成员都能移动构造或移动赋值时，编译器才会为它合成移动构造函数或移动赋值运算符。
    // 与拷贝操作不同，移动操作永远不会隐式定义为删除的函数。
    // 但是，如果我们显式地要求编译器生成=default的（参见7.1.4节，第237页）移动操作，且编译器不能移动所有成员，则编译器会将移动操作定义为删除的函数。
    // · 类似拷贝构造函数，如果类的析构函数被定义为删除的或不可访问的，则类的移动构造函数被定义为删除的。
    // · 类似拷贝赋值运算符，如果有类成员是const的或是引用，则类的移动赋值运算符被定义为删除的。
    // 移动操作和合成的拷贝控制成员间还有最后一个相互作用关系：一个类是否定义了自己的移动操作对拷贝操作如何合成有影响。
    // 如果类定义了一个移动构造函数和/或一个移动赋值运算符，则该类的合成拷贝构造函数和拷贝赋值运算符会被定义为删除的。
    // 定义了一个移动构造函数或移动赋值运算符的类必须也定义自己的拷贝操作。否则，这些成员默认地被定义为删除的。

    // 移动右值，拷贝左值
    // 如果一个类既有移动构造函数，也有拷贝构造函数，编译器使用普通的函数匹配规则来确定使用哪个构造函数（参见6.4节，第208页）。赋值操作的情况类似。
    // 在我们的StrVec类中，拷贝构造函数接受一个const StrVec的引用。因此，它可以用于任何可以转换为StrVec的类型。而移动构造函数接受一个StrVec&&，因此只能用于实参是（非static）右值的情形：
    StrVec v1, v2;
    v1 = v2;                  // v2是左值，使用拷贝赋值
    StrVec getVec(istream &); // getVec返回一个右值
    v2 = getVec(cin);         // getVec(cin)是一个右值，使用移动赋值

    // ……但如果没有移动构造函数，右值也被拷贝
    // 如果一个类有一个拷贝构造函数但未定义移动构造函数，会发生什么呢？在此情况下，编译器不会合成移动构造函数，这意味着此类将有拷贝构造函数但不会有移动构造函数。
    // 如果一个类没有移动构造函数，函数匹配规则保证该类型的对象会被拷贝，即使我们试图通过调用move来移动它们时也是如此：
    Foo fx;
    Foo fy(fx);            // 拷贝构造函数，x是一个左值
    Foo fz(std::move(fx)); // 拷贝构造函数，因为未定义移动构造函数
    // 值得注意的是，用拷贝构造函数代替移动构造函数几乎肯定是安全的（赋值运算符的情况类似）。
    // 一般情况下，拷贝构造函数满足对应的移动构造函数的要求：它会拷贝给定对象，并将原对象置于有效状态。实际上，拷贝构造函数甚至都不会改变原对象的值。
    // 如果一个类有一个可用的拷贝构造函数而没有移动构造函数，则其对象是通过拷贝构造函数来“移动”的。拷贝赋值运算符和移动赋值运算符的情况类似。

    // 拷贝并交换赋值运算符和移动操作
    // 我们的HasPtr版本定义了一个拷贝并交换赋值运算符（参见13.3节，第459页），它是函数匹配和移动操作间相互关系的一个很好的示例。
    // 如果我们为此类添加一个移动构造函数，它实际上也会获得一个移动赋值运算符：
    // 现在让我们观察赋值运算符。此运算符有一个非引用参数，这意味着此参数要进行拷贝初始化（参见13.1.1节，第441页）。
    // 依赖于实参的类型，拷贝初始化要么使用拷贝构造函数，要么使用移动构造函数——左值被拷贝，右值被移动。因此，单一的赋值运算符就实现了拷贝赋值运算符和移动赋值运算符两种功能。
    HasPtr hp, hp2;
    hp = hp2;            // hp2是一个左值，hp2通过拷贝构造函数来拷贝
    hp = std::move(hp2); // 移动构造函数移动hp2
    // 在第二个赋值中，我们调用std：：move将一个右值引用绑定到hp2上。
    // 在此情况下，拷贝构造函数和移动构造函数都是可行的。但是，由于实参是一个右值引用，移动构造函数是精确匹配的。移动构造函数从hp2拷贝指针，而不会分配任何内存。

    // 建议：更新三/五法则
    // 所有五个拷贝控制成员应该看作一个整体：一般来说，如果一个类定义了任何一个拷贝操作，它就应该定义所有五个操作。
    // 如前所述，某些类必须定义拷贝构造函数、拷贝赋值运算符和析构函数才能正确工作（参见13.1.4节，第447页）。
    // 一般来说，拷贝一个资源会导致一些额外开销。在这种拷贝并非必要的情况下，定义了移动构造函数和移动赋值运算符的类就可以避免此问题。

    // 移动迭代器
    // 新标准库中定义了一种移动迭代器（move iterator）适配器（参见10.4节，第358页）
    // 一个移动迭代器通过改变给定迭代器的解引用运算符的行为来适配此迭代器。
    // 一般来说，一个迭代器的解引用运算符返回一个指向元素的左值。与其他迭代器不同，移动迭代器的解引用运算符生成一个右值引用。
    // 我们通过调用标准库的make_move_iterator函数将一个普通迭代器转换为一个移动迭代器。此函数接受一个迭代器参数，返回一个移动迭代器。
    // uninitialized_copy对输入序列中的每个元素调用construct来将元素“拷贝”到目的位置。
    // 此算法使用迭代器的解引用运算符从输入序列中提取元素。由于我们传递给它的是移动迭代器，因此解引用运算符生成的是一个右值引用，这意味着construct将使用移动构造函数来构造元素。

    // 建议：不要随意使用移动操作
    // 建议：不要随意使用移动操作由于一个移后源对象具有不确定的状态，对其调用std：：move是危险的。当我们调用move时，必须绝对确认移后源对象没有其他用户。
    // 通过在类代码中小心地使用move，可以大幅度提升性能。而如果随意在普通用户代码（与类实现代码相对）中使用移动操作，很可能导致莫名其妙的、难以查找的错误，而难以提升应用程序性能。
    // 在移动构造函数和移动赋值运算符这些类实现代码之外的地方，只有当你确信需要进行移动操作且移动操作是安全的，才可以使用std：：move。

    
    return 0;
}